package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/5 19:01
 */
public class J68 {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    class Info {
        boolean findp;
        boolean findq;
        TreeNode ans;

        public Info(boolean findp, boolean findq, TreeNode ans) {
            this.findp = findp;
            this.findq = findq;
            this.ans = ans;
        }
    }

    // https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p, q).ans;
    }

    private Info find(TreeNode head, TreeNode p, TreeNode q) {
        if(head == null) {
            return new Info(false, false, null);
        }
        Info lInfo = find(head.left, p, q);
        Info rInfo = find(head.right, p, q);
        boolean findp = lInfo.findp || rInfo.findp || head == p;
        boolean findq = lInfo.findq || rInfo.findq || head == q;
        TreeNode ans = null;
        if(lInfo.findp && lInfo.findq) {
            ans = lInfo.ans;
        }else if(rInfo.findp && rInfo.findq) {
            ans = rInfo.ans;
        }else {
            if(findp && findq) {
                ans = head;
            }
        }
        return new Info(findp, findq, ans);
    }

}
